P8054 题解

题目链接

我们只需尽可能的在区间 $(1,n)$ 内寻找质因子数量最多的数，再与 $n$ 的质因子数量比较即可。

考虑到 $2^k$ 增长速度相比于其他质数 $p^k$ 要慢，而对于和 $2^k$ 大小相近的数，他们的质因子个数不可能比 $2^k$ 要多。

我们可以感性理解这一件事情，于是我们就得到了第一个结论：

• 在区间 $(1,n)$ 中，质因子个数最多的数为最大的形如 $2^k$ 的数，即找到 $2^k \lt n \le 2^{k+1}$。

这一件事情可以在 $O(\log n)$ 的时间内做到。

然后就可以去比较 $n$ 的质因子个数与 $k$ 的大小了。

由于 $n \le 10^{18}$，分解质因数 $O(\sqrt{n})$ 的方式肯定是不可行的，那我们便使用一些奇技淫巧更高端的技巧。

我们考虑 $n$ 的一些特殊情况：

1. 当 $n$ 为奇数时，$n$ 中不含有质因子 $2$，此时我们可以感性理解一下，要想用奇质数乘出大小差不多的数，用到的质数个数会更少，所以 $n$ 的质因子个数必定小于 $k$，即 $f(n)<k$。

2. 当 $n=2^{k+1}$ 时，此时虽然 $2^k$ 已经是最大的了，但 $n$ 中有 $k+1$ 个质因子，所以 $n$ 的质因子个数大于 $k$ ，即 $f(n)>k$。

3. 当 $n=2^{k-1} \times 3$ 时，此时 $n$ 正好介于 $2^k$ 与 $2^{k+1}$ 之间，但质因子个数也是 $k$，故 $f(n)=k$。

4. 对于其他的偶数 $n$，我们可以用第一类中的方法类似理解一下，质因子个数应该也是小于 $k$ 的，即 $f(n)<k$。

综上所述，我们便可以用特判的方法过掉这一道题了，时间复杂度 $O(T\log n)$ 。

还有就是注意一些细节，比如左移记得要用 long long 。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long n; scanf("%lld", &n);
        int k = 0;
        while (1LL << (k + 1) < n) k++;
        if (n >= 5 && n % 2 == 1) puts("1");
        else if (n % 3 == 0 && 1LL << (k - 1) == n / 3) puts("0");
        else if (n % 2 == 0 && 1LL << (k + 1) == n) puts("0");
        else puts("1");
    }
}